#include<iostream>
#include<vector>
using namespace std;
/*
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
解题思路：
首先要定义dp数组dp[i][j]表示在nums1中以i-1下标为结尾的元素与nums2中以j-1下标为结尾的元素的最长公共子序列
所以有递推公式:if(nums1[i-1]==nums2[j-1])dp[i][j] = dp[i-1][j-1]+1
在初始化时需要注意,dp[i][0]和dp[0][j]由于没有意义，所以要初始化为0
*/
int dp(vector<int> nums1,vector<int> nums2)
{
    //创建二维dp数组
    vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1));
    for(int i=0;i<=nums1.size();i++)
        dp[i][0] = 0;
    for(int j=0;j<=nums2.size();j++)
        dp[0][j] = 0;
    //遍历dp
    int result = 0;
    for(int i=1;i<=nums1.size();i++)
    {
        for(int j=1;j<=nums2.size();j++)
        {
            if(nums1[i-1]==nums2[j-1])
                dp[i][j] = dp[i-1][j-1]+1;
            if(dp[i][j]>result)
                result = dp[i][j];
        }
    }
    return result;
}
int main()
{
    cout<<"enter a number:"<<endl;
    int number1;
    cin>>number1;
    cout<<"enter nums1:"<<endl;
    vector<int> nums1(number1);
    for(int i=0;i<number1;i++)
    {
        cin>>nums1[i];
    }
    cout<<"enter a number:"<<endl;
    int number2;
    cin>>number2;
    cout<<"enter nums2:"<<endl;
    vector<int> nums2(number2);
    for(int i=0;i<number2;i++)
        cin>>nums2[i];
    cout<<dp(nums1,nums2);
    return 0;
}